Computer networks over which a message may be transmitted are either connection-oriented or connectionless.
A connection-oriented computer network is one in which a dedicated connection is identified for transmitting a message. If the connection-oriented network fails (e.g., the message isn't transmitted, the message is corrupted) at any point during the transmission of the message, the entire message must be retransmitted once the connection-oriented network is reestablished. If the connection is reliable, the connection-oriented network is the fastest way to transmit a message.
A connectionless computer network is one in which no dedicated connection is identified for transmitting a message, but one in which numerous available network connections are used to transmit a message. A message to be transmitted over a connectionless network is broken up into numerous packets, and the packets are transmitted over any available network connection to the intended recipient. Between the sender and the intended final recipient, there may be a number of intermediate recipients that must receive and reconstruct the packets for further transmission. In a connectionless network such as an Internet Protocol (IP) network, the packets to be transmitted, most likely, will be transmitted over a number of different network connections and will be received out of order by the recipient. Additional information is added to each packet prior to transmission to identify the message to which a packet pertains and its position within the message so that the recipient may reconstruct the message. If the transmission of a packet over a network connection fails then only those packets that were not properly transmitted must be retransmitted and not the entire message. The recipient of a message sent over a connectionless network sends messages, commonly referred to as acknowledgment messages, to inform the sender which packets were received (i.e., a positive acknowledgment message) or which packets were not received (i.e., a negative acknowledgment message). The sender uses the acknowledgment message to determine which packets to retransmit to the recipient. The sender keeps a copy of each packet sent until it receives a message from the recipient that indicates that the packet was received. Connectionless networks decrease the likelihood that an entire message must be retransmitted, but increase the likelihood that some of the packets of a message must be retransmitted.
Technological advancements continue to decrease the time it takes to transmit a packet. These improvements in speed make it more feasible to transmit messages containing large amounts of data such as photographs. With an increase in the size of messages being sent comes an increase in the number of packets that must be retransmitted and an increase in the number of acknowledgment messages that are sent. An increase in acknowledgement messages comes at a time when the network connections are less likely to transmit them reliably, causing even more acknowledgement messages to be sent.
Prior art methods record the length of a group of packets received that start with the first packet of the message (i.e., a complete pointer), record the number of the highest numbered packet received (i.e., a current pointer), store each packet that is out of order, and record the number of each missing packets, where the highest packet number received is assumed to be the end of the message (this assumption may prove incorrect). In such a scheme, a received packet is compared to the recorded data to determine if the received packet is a duplicate and should be discarded or a missing packet that must be stored on the out-of-order list, or further transmitted because it is the next packet in a contiguous string of packets starting with the first packet (i.e., an expected packet). The number of steps that are required by such a method to determine if a received packet is a duplicate is 1+n in the worst case and 1+n/2 in the average case, and 1 in the best case, where n is the number of packets that are out of order. The number of steps that are required by this method to identify the received packet as a missing frame is 3+n in the worst case, 3+n/2 in the average case, and 3 in the best case. This method requires that the entire list of out-of-order packets be searched prior to sending an acknowledgment message. So, the time to send an acknowledgment message increases with the number of packets received that are out of order. As messages increase in size, the number of packets received that are out of order are expected to grow and, therefore, the time it takes to send an acknowledgment message is expected to increase. So, there is a need for a more efficient method of acknowledging the receipt of packets and reassemble the same for further transmission. The present invention is just such a method.
U.S. Pat. No. 5,553,083, entitled “METHOD FOR QUICKLY AND RELIABLY TRANSMITTING FRAMES OF DATA OVER COMMUNICATIONS LINKS,” discloses a method of a receiver sending acknowledgments (i.e., messages indicating which packets were received) while the sender is sending data but does not disclose the method of the present invention. U.S. Pat. No. 5,553,083 is hereby incorporated by reference into the specification of the present invention.
U.S. Pat. No. 5,727,002, entitled “METHOD FOR TRANSMITTING DATA,” discloses a method of a receiver sending negative acknowledgments (i.e., messages that indicate which packets were not received) while the sender is sending data but does not disclose the method of the present invention. U.S. Pat. No. 5,727,002 is hereby incorporated by reference into the specification of the present invention.
U.S. Pat. No. 5,815,667, entitled “CIRCUITS AND METHODS FOR INTELLIGENT ACKNOWLEDGEMENT BASED FLOW CONTROL IN A PROCESSING SYSTEM NETWORK,” discloses a device for and method of monitoring and adjusting the utilization level of a network and the transmission delay of an acknowledgment signal but does not disclose the method of the present invention. U.S. Pat. No. 5,815,667 is hereby incorporated by reference into the specification of the present invention.
U.S. Pat. No. 6,252,851, entitled “METHOD FOR REGULATING TCP FLOW OVER HETEROGENEOUS NETWORKS,” discloses a method of releasing acknowledgment signals in a time released manner to avoid overflow of the packet buffer due to bandwidth limitations but does not disclose the method of the present invention. U.S. Pat. No. 6,252,851 is hereby incorporated by reference into the specification of the present invention.
U.S. Pat. No. 6,282,172, entitled “GENERATING ACKNOWLEDGEMENT SIGNALS IN A DATA COMMUNICATION SYSTEM,” discloses a method of generating an acknowledgment signals upon receipt of a data packet but before the data packet is completely received, preventing the sender from reducing the data rate of the transmission due to high latency or asymmetry of the communication link, but does not disclose the method of the present invention. U.S. Pat. No. 6,282,172 is hereby incorporated by reference into the specification of the present invention.